/*
 * ZhuTakaoka.cpp
 *
 *  Created on: 27-08-2013
 *      Author: Krzychu
 */

#include "ZhuTakaoka.h"

#include "Config.h"

#define MAX(a, b) (a > b) ? a : b
#define ASIZE 255

ZhuTakaoka::ZhuTakaoka()
{

}

ZhuTakaoka::~ZhuTakaoka()
{

}

std::string ZhuTakaoka::getName()
{
	return "Zhu-Takaoka";
}

int** preZtBc(std::string pattern)
{
	int** result = new int*[ASIZE];
	int i, j;

	int patternSize = pattern.size();

	for (i = 0; i < ASIZE; ++i)
	{
		result[i] = new int[ASIZE];
		for (j = 0; j < ASIZE; ++j)
		{
			result[i][j] = patternSize;
		}
	}
	for (i = 0; i < ASIZE; ++i)
	{
		result[i][pattern[0]] = patternSize - 1;
	}
	for (i = 1; i < patternSize - 1; ++i)
	{
		result[pattern[i - 1]][pattern[i]] = patternSize - 1 - i;
	}

	return result;
}

searchResult ZhuTakaoka::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

		int i, j;

		int textSize = text.size();
		int patternSize = pattern.size();

		/* Preprocessing */
		int** ztBc = preZtBc(pattern);
		int* bmGs = pre_good_suffix_shift(pattern);

		/* Searching */
		j = 0;
		while (j <= textSize - patternSize)
		{
			result.iterationsTaken++;
			i = patternSize - 1;
			while (i < patternSize && pattern[i] == text[i + j])
			{
				--i;
			}
			if (i < 0)
			{
				result.positionsFound.push_back(j);
				if (Config::getInstance()->getFindOneOccurence())
				{
					return result;
				}
				j += bmGs[0];
			}
			else
			{
				j += MAX(bmGs[i], ztBc[text[j + patternSize - 2]][text[j + patternSize - 1]]);
			}
		}

	return result;
}
